package com.xixi.basicAlgroithms;

import java.util.ArrayList;
import java.util.List;

/**
 * 排列：如果要想在 n 个物品中，按顺序的选择 k 个物品，那么选择的方式总共有这么多种
 * @author vincentML
 * @date 2022-04-13  13:49
 */

public class Permutation {


    public List<List<Integer>> result = new ArrayList<>();
    public static void main(String[] args) {

        Permutation permutation = new Permutation();
        System.out.println( permutation.permutation(new int[]{1,2,3,4,5}, 3));
        System.out.println( permutation.result.size());


    }


    public List<List<Integer>> permutation(int[] nums, int k){

        //nums中取k个数字，有多少种顺序

        backTracking(nums, nums.length, k, new ArrayList<>());

        return result;
    }

    /*
     * @Desc:
     * @Author vincentML
     * @Date: 2022/4/13 13:54
     * @param nums  数字集合
     * @param nLength nums的长度
     * @param k 取多少个数
     * @param index 当前取到第几个数
    */
    public void backTracking(int[] nums, int nLength, int k, List<Integer> path){
        if(path.size() == k){ //取够了
            result.add(new ArrayList<>(path)); //快照
            return;
        }

        //取当前的数

        for(int i = 0; i < nLength; ++i){
            if(path.contains(nums[i])) continue; //如果当前数取过了就不取了
            path.add(nums[i]); //路径里加上当前值
            backTracking(nums, nLength, k, path);
            path.remove(path.size() -1); //路径删除最后的值
        }




    }

}
